import sys
# Install gurobi
!{sys.executable} -m pip install -i https://pypi.gurobi.com gurobipy
!{sys.executable} -m pip install plotly geopy

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import pandas as pd
from itertools import product

import gurobipy as gp
from gurobipy import GRB, quicksum

# These are ours
import problem
import visualization

Looking in indexes: https://pypi.gurobi.com
Requirement already satisfied: gurobipy in /opt/anaconda3/lib/python3.8/site-packages (9.1.1)
Requirement already satisfied: plotly in /opt/anaconda3/lib/python3.8/site-packages (4.14.3)
Requirement already satisfied: geopy in /opt/anaconda3/lib/python3.8/site-packages (2.1.0)
Requirement already satisfied: retrying>=1.3.3 in /opt/anaconda3/lib/python3.8/site-packages (from plotly) (1.3.3)
Requirement already satisfied: six in /opt/anaconda3/lib/python3.8/site-packages (from plotly) (1.15.0)
Requirement already satisfied: geographiclib<2,>=1.49 in /opt/anaconda3/lib/python3.8/site-packages (from geopy) (1.50)

def normalize(i, j):
    assert i != j
    return (i, j) if i < j else (j, i)

Problem configuration

from model import Autonomax, Config

# Run on the first |C| cities (mostly for testing)
C = 41

# What scenario we will be utilizing
scenario = 0
# The number of cities in the core net
NC = 4
# 1 if the core net should be a cycle; 0 if it shoul be a path.
Z = 0

autonomax = Autonomax(
    Config(
        cities=problem.cities[:C],
        distances=problem.D[:C, :C],
        demand=problem.B[scenario][:C],
        core_city_count=NC,
        core_net_is_cycle=Z,
    )
)

Academic license - for non-commercial use only - expires 2021-05-15
Using license file /Users/sjurwold/gurobi.lic

A = autonomax.model.getA()

count = lambda d: len(d) if isinstance(d, gp.tupledict) else 1

V = sum(count(v) for v in autonomax.variables.values())
C = sum(count(c) for c in autonomax.constraints.values())

print(f'V = {V}, C = {C}')

fig, ax = plt.subplots(1, figsize=(128, 128 * C/V))
ax.set_xticklabels([])
ax.set_yticklabels([])
plt.spy(A)


total = 0
print(f'\nCONSTRAINT SETS:')
for (name, constraint) in autonomax.constraints.items():
    constraints_in_set = count(constraint)
    print(f'{constraints_in_set:>5} | {name}')
    #plt.gcf().text(0.07, 0.69 - 0.4 * (total + 0.5 * count(constraint)) / C, name, fontsize=14)
    total += constraints_in_set
    plt.plot([0, V], [total - 0.5, total - 0.5], color='grey')
    
total = 0
print(f'\nVARIABLE SETS:')
for (name, variables) in autonomax.variables.items():
    variables_in_set = count(variables)
    print(f'{variables_in_set:>5} | {name}')
    #plt.gcf().text(0.1 + 0.8 * (total + 0.5*count(variables)) / V, 0.8, name, fontsize=14)
    total += count(variables)
    plt.plot([total - 0.5, total - 0.5], [0, C], color='grey')
    
plt.savefig('constraint-matrix.png', dpi=200)

V = 9389, C = 6153

CONSTRAINT SETS:
    1 | one_control_center
   41 | control_city_directly_connected
 1681 | reduce_control_center_symmetry
   41 | core_city_ub
    1 | cycle_or_path
   41 | disallow_core_tree
    1 | exactly_nc_core_cities
   41 | control_center_is_connected
 2460 | is_connectable
  123 | is_connected_timestep
   41 | connected_graph
   41 | conservation_of_flow
  820 | force_edge_if_flow
  820 | edge_cost_lb

VARIABLE SETS:
   41 | is_control_center
  820 | is_core_edge
   41 | is_core_city
  164 | is_connected_step
 5043 | is_connectable_step
  820 | flow
  820 | abs_flow
  820 | is_sub_edge
  820 | edge_cost

autonomax.model.Params.timeLimit = 600.0
autonomax.model.optimize()

Changed value of parameter timeLimit to 600.0
   Prev: inf  Min: 0.0  Max: inf  Default: inf
Gurobi Optimizer version 9.1.1 build v9.1.1rc0 (mac64)
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 6153 rows, 9389 columns and 30299 nonzeros
Model fingerprint: 0x620c19f9
Model has 820 general constraints
Variable types: 2460 continuous, 6929 integer (6929 binary)
Coefficient statistics:
  Matrix range     [1e+00, 2e+05]
  Objective range  [1e+00, 2e+04]
  Bounds range     [1e+00, 1e+02]
  RHS range        [7e-01, 4e+01]
Presolve removed 93 rows and 2633 columns
Presolve time: 0.09s
Presolved: 6060 rows, 6756 columns, 30309 nonzeros
Variable types: 2460 continuous, 4296 integer (4296 binary)
Found heuristic solution: objective 84902.481928

Root relaxation: objective 1.063333e+03, 5492 iterations, 0.13 seconds

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

     0     0 1063.33250    0  184 84902.4819 1063.33250  98.7%     -    0s
H    0     0                    28631.686435 2393.79536  91.6%     -    0s
     0     0 2393.79536    0  257 28631.6864 2393.79536  91.6%     -    0s
     0     0 2520.28857    0  269 28631.6864 2520.28857  91.2%     -    0s
     0     0 2520.28857    0  269 28631.6864 2520.28857  91.2%     -    0s
     0     0 2780.84720    0  254 28631.6864 2780.84720  90.3%     -    0s
     0     0 2780.84720    0  213 28631.6864 2780.84720  90.3%     -    1s
H    0     0                    19492.252419 2780.84720  85.7%     -    1s
     0     2 2780.84720    0  207 19492.2524 2780.84720  85.7%     -    1s
H   35    38                    19411.617554 2780.84720  85.7%   481    2s
H   76    83                    17295.249235 2780.84720  83.9%   251    2s
H   77    83                    15614.862409 2780.84720  82.2%   248    2s
H  115   112                    15582.290546 2780.84720  82.2%   190    2s
H  117   112                    15569.777327 2780.84720  82.1%   188    2s
H  122   112                    15462.774083 2780.84720  82.0%   183    2s
H  687   632                    15356.400285 2780.84720  81.9%   105    5s
H  688   632                    15318.120046 2780.84720  81.8%   105    5s
H  694   632                    15277.960562 2780.84720  81.8%   105    5s
H  737   676                    14907.429344 2780.84720  81.3%   104    5s
H  740   672                    14813.759399 2780.84720  81.2%   104    5s
H  741   663                    14668.480296 2780.84720  81.0%   104    5s
H 1320  1209                    14633.515764 2780.84720  81.0%  96.9    6s
H 1495  1333                    14621.890697 2780.84720  81.0%  98.3    7s
  1500  1337 8342.16063   47  253 14621.8907 2780.84720  81.0%  98.0   10s
  1508  1347 2780.84720   14  243 14621.8907 2780.84720  81.0%   109   15s
H 1580  1303                    14576.559761 2851.56500  80.4%   122   19s
  1582  1310 9826.39889   20  314 14576.5598 2851.56500  80.4%   123   20s
H 1614  1262                    14564.917353 2887.15121  80.2%   127   21s
H 1615  1200                    14423.931717 2887.15121  80.0%   127   21s
H 1675  1157                    14398.780590 3056.98068  78.8%   130   23s
H 1682  1101                    14398.274528 3082.34056  78.6%   130   23s
H 1713  1072                    13993.418491 3087.42366  77.9%   132   24s
  1778  1084 3115.30718   27  270 13993.4185 3115.30718  77.7%   133   25s
H 1798  1027                    13950.457402 3116.36909  77.7%   134   25s
  2344  1112 4140.88402   39  222 13950.4574 3209.54117  77.0%   137   30s
  3036  1380 5543.08580   57  148 13950.4574 3209.54117  77.0%   135   35s
  4047  1691 8613.18608   64  111 13950.4574 3353.41248  76.0%   135   40s
H 5083  2474                    13886.992252 4145.20532  70.2%   130   44s
  5174  2499 7451.17708   58  119 13886.9923 4145.20532  70.2%   129   45s
H 5242  2675                    13799.296440 4193.02558  69.6%   128   46s
  6035  3148     cutoff   23      13799.2964 4332.20289  68.6%   130   50s
  6981  3524 9715.80260   36  162 13799.2964 4518.48589  67.3%   133   55s
  7849  4110 11336.3171   34  138 13799.2964 4644.50648  66.3%   134   60s
H 7873  4110                    13799.296438 4644.50648  66.3%   134   60s
H 8256  4229                    13799.296422 4703.86453  65.9%   133   61s
  9253  4905 6463.13267   22  276 13799.2964 4845.05202  64.9%   130   65s
H 9264  4905                    13799.296368 4845.05202  64.9%   130   65s
H 9854  5310                    13799.296350 5009.61261  63.7%   132   67s
H10044  5310                    13799.296331 5031.95305  63.5%   132   67s
H10271  5310                    13799.296329 5064.22110  63.3%   132   67s
H10650  5591                    13799.296316 5141.69220  62.7%   133   71s
H10747  5591                    13799.296289 5141.69220  62.7%   133   71s
H11005  5774                    13799.296271 5141.69220  62.7%   134   73s
 11817  6313 6447.85504   46  249 13799.2963 5387.01793  61.0%   134   76s
 12755  6539     cutoff   22      13799.2963 5597.99805  59.4%   134   80s
H13018  6768                    13799.296106 5674.82574  58.9%   135   82s
 13949  7339 9037.92367   56   97 13799.2961 5794.34937  58.0%   135   86s
 15433  7941 10227.7781   46  170 13799.2961 6075.99880  56.0%   134   91s
 15622  8233 12262.8795   68   85 13799.2961 6121.75103  55.6%   134   97s
 16126  8558 9423.16593   54  181 13799.2961 6229.98854  54.9%   134  100s
H16455  8558                    13799.296087 6243.99721  54.8%   134  100s
 17223  9266 11483.5706   45  147 13799.2961 6342.25312  54.0%   134  105s
H17342  9212                    13627.031901 6342.25312  53.5%   133  105s
H18607  9441                    13378.777498 6490.04688  51.5%   132  108s
 18771  9716 7754.47021   51  180 13378.7775 6523.74384  51.2%   132  111s
 19979 10447 12246.9337   44  146 13378.7775 6672.79292  50.1%   133  117s
 20991 10690     cutoff   36      13378.7775 6868.10445  48.7%   132  120s
 22800 11375 7801.64506   33  259 13378.7775 7057.68130  47.2%   133  125s
 24759 11973 8276.95244   70   82 13378.7775 7316.07080  45.3%   134  131s
 26399 12296 10570.8011   29  194 13378.7775 7548.60818  43.6%   134  136s
 27998 12501 13179.4243   38  154 13378.7775 7861.57061  41.2%   136  142s
 28308 12935 12485.4717   61  111 13378.7775 7916.69948  40.8%   136  145s
 29323 13291 10049.7194   38  244 13378.7775 8021.66004  40.0%   136  186s
H30037 13291                    13378.777410 8050.98600  39.8%   136  186s
 30774 13478 10928.0072   45  216 13378.7774 8228.60537  38.5%   138  212s
 31133 13606 11356.4753   87  120 13378.7774 8281.72350  38.1%   140  215s
 32031 13773     cutoff   36      13378.7774 8382.80360  37.3%   144  223s
H32249 13773                    13378.777365 8385.83573  37.3%   145  223s
 32664 13827 13357.7506   43  205 13378.7774 8453.04176  36.8%   146  227s
 33330 13886     cutoff   71      13378.7774 8490.39284  36.5%   149  232s
H33334 13886                    13378.777344 8490.39284  36.5%   149  232s
 33878 14002 9161.55255   44  230 13378.7773 8593.04176  35.8%   152  237s
 34405 14130 13190.2708   31  379 13378.7773 8645.63227  35.4%   155  242s
 35061 14269     cutoff   54      13378.7773 8689.82248  35.0%   157  248s
 35762 14340 13258.1183   52  279 13378.7773 8768.18662  34.5%   160  253s
 36015 14434 12320.8916   48  120 13378.7773 8772.78893  34.4%   160  259s
 36645 14674 13236.0394   54  178 13378.7773 8856.75189  33.8%   163  264s
 37325 14730 10143.8589   69  261 13378.7773 8881.03435  33.6%   166  270s
 37804 14835 13137.9610   43  241 13378.7773 8935.68867  33.2%   169  275s
 38435 15094 12361.9921   35  176 13378.7773 8950.94495  33.1%   171  281s
 39328 15237     cutoff   49      13378.7773 9039.22929  32.4%   173  288s
 39926 15238     cutoff   91      13378.7773 9080.48068  32.1%   175  294s
 40556 15391 10914.6259   91  226 13378.7773 9099.32872  32.0%   177  300s
 41376 15639 9816.14609   44  250 13378.7773 9158.13054  31.5%   179  306s
 42252 15728 11467.9326   81  136 13378.7773 9248.01404  30.9%   181  334s
 42705 15813     cutoff   82      13378.7773 9259.92798  30.8%   182  340s
 43446 15853 11477.9641   29  305 13378.7773 9332.51189  30.2%   185  346s
 43873 16010 10627.1030   68  209 13378.7773 9358.53918  30.0%   187  351s
 44442 16102     cutoff   47      13378.7773 9414.80638  29.6%   188  357s
 45132 16211 11222.8843   80  145 13378.7773 9447.73548  29.4%   191  364s
 45770 16272 10079.9662   44  159 13378.7773 9485.73154  29.1%   193  371s
 46711 16334 10763.8061   76  180 13378.7773 9518.53993  28.9%   195  381s
 47077 16488 12304.6531   63  159 13378.7773 9546.05397  28.6%   196  392s
 48118 16550     cutoff   63      13378.7773 9593.81374  28.3%   198  399s
 48892 16722 11366.1111  117  157 13378.7773 9627.70035  28.0%   201  405s
 49844 16810     cutoff   63      13378.7773 9704.97579  27.5%   203  412s
 50692 16943 10387.9477   70  218 13378.7773 9728.16626  27.3%   205  418s
 51444 16998     cutoff   75      13378.7773 9782.19316  26.9%   207  766s

Cutting planes:
  Gomory: 83
  Cover: 315
  Implied bound: 42
  MIR: 232
  StrongCG: 4
  Flow cover: 607
  Inf proof: 35
  Zero half: 14
  RLT: 311
  Relax-and-lift: 44

Explored 51869 nodes (10757862 simplex iterations) in 766.35 seconds
Thread count was 8 (of 8 available processors)

Solution count 10: 13378.8 13378.8 13627 ... 14398.8

Time limit reached
Best objective 1.337877734422e+04, best bound 9.787365231096e+03, gap 26.8441%

Solution

city_info = pd.DataFrame(autonomax.city_info())
city_info

	Index	Name	IsCoreCity	IsControlCenter	Demand	IngoingFlow	OutgoingFlow
0	0	Boden	False	False	4.5	4.000000e+00	8.500000e+00
1	1	Borås	False	False	0.7	1.030000e+01	1.100000e+01
2	2	Eskilstuna	False	False	1.1	1.421085e-13	1.099999e+00
3	3	Falun	False	False	2.3	1.278977e-13	2.300000e+00
4	4	Gävle	False	False	1.0	8.900000e+00	9.900000e+00
5	5	Göteborg	False	False	5.8	3.481659e-13	5.800000e+00
6	6	Halmstad	False	False	3.4	6.100000e+00	9.500000e+00
7	7	Haparanda	False	False	4.6	0.000000e+00	4.600000e+00
8	8	Helsingborg	False	False	2.2	3.900000e+00	6.100000e+00
9	9	Hudiksvall	True	False	3.9	2.740000e+01	3.130000e+01
10	10	Jönköping	False	False	1.2	1.300000e+01	1.420000e+01
11	11	Kalmar	False	False	4.0	1.016076e-12	4.000000e+00
12	12	Karlskrona	False	False	1.6	5.684342e-13	1.600000e+00
13	13	Karlstad	False	False	0.9	1.222134e-12	9.000008e-01
14	14	Kiruna	False	False	4.0	1.278977e-13	4.000000e+00
15	15	Kristianstad	False	False	3.0	5.471179e-13	3.000000e+00
16	16	Lidköping	False	False	1.2	1.340000e+01	1.460000e+01
17	17	Linköping	False	False	4.1	1.800000e+00	5.900000e+00
18	18	Luleå	False	False	2.0	1.310000e+01	1.510000e+01
19	19	Malmö	False	False	2.6	1.300000e+00	3.900000e+00
20	20	Motala	False	False	2.4	5.900000e+00	8.300000e+00
21	21	Norrköping	False	False	1.7	1.705303e-12	1.700000e+00
22	22	Nyköping	False	False	4.6	2.110312e-12	4.600000e+00
23	23	Sandviken	True	False	4.5	4.350000e+01	4.800000e+01
24	24	Skellefteå	False	False	4.4	1.510000e+01	1.950000e+01
25	25	Skövde	True	False	2.5	3.980000e+01	4.230000e+01
26	26	Stockholm	False	False	7.0	1.239897e-12	7.000000e+00
27	27	Sundsvall	False	False	0.7	2.670000e+01	2.740000e+01
28	28	Trelleborg	False	False	1.3	1.548983e-12	1.300000e+00
29	29	Uddevalla	False	False	4.0	5.800000e+00	9.800000e+00
30	30	Umeå	False	False	3.2	1.950000e+01	2.270000e+01
31	31	Uppsala	False	False	1.9	7.000000e+00	8.900000e+00
32	32	Varberg	True	True	0.8	9.500000e+00	1.030000e+01
33	33	Vetlanda	False	False	2.1	1.090000e+01	1.300000e+01
34	34	Vänersborg	False	False	3.6	9.800000e+00	1.340000e+01
35	35	Västervik	False	False	1.8	2.891909e-12	1.800000e+00
36	36	Västerås	False	False	1.4	2.373213e-12	1.400000e+00
37	37	Växjö	False	False	2.3	4.600000e+00	6.900000e+00
38	38	Örebro	True	True	4.1	1.083000e+02	1.030287e-13
39	39	Örnsköldsvik	False	False	3.1	2.270000e+01	2.580000e+01
40	40	Östersund	False	False	0.9	8.100187e-13	9.000000e-01

edge_info = pd.DataFrame(autonomax.edge_info())
edge_info

	From	To	Type	Flow	Cost	Distance
0	Skellefteå	Umeå	SUB	19.500000	731.139160	111
1	Skövde	Örebro	CORE	42.299999	1319.999985	132
2	Karlskrona	Växjö	SUB	1.600000	62.121900	102
3	Motala	Örebro	SUB	8.300000	241.611348	92
4	Boden	Kiruna	SUB	-4.000000	637.913000	291
5	Nyköping	Örebro	SUB	4.600000	228.104575	131
6	Hudiksvall	Sandviken	CORE	31.300000	1319.999985	132
7	Sundsvall	Östersund	SUB	-0.900000	70.870188	166
8	Halmstad	Helsingborg	SUB	-6.100000	145.447337	79
9	Jönköping	Vetlanda	SUB	-13.000000	225.433574	65
10	Umeå	Örnsköldsvik	SUB	22.700000	849.479945	111
11	Boden	Luleå	SUB	8.500000	58.656839	32
12	Lidköping	Skövde	SUB	14.600000	168.360541	49
13	Eskilstuna	Örebro	SUB	1.099999	36.303256	83
14	Karlstad	Örebro	SUB	0.900001	29.229986	77
15	Halmstad	Varberg	SUB	9.500000	167.432227	65
16	Lidköping	Vänersborg	SUB	-13.400000	206.938975	60
17	Uddevalla	Vänersborg	SUB	9.800000	39.823253	21
18	Gävle	Sandviken	SUB	9.900000	49.133186	25
19	Linköping	Motala	SUB	5.900000	77.952787	51
20	Linköping	Västervik	SUB	-1.800000	64.378861	97
21	Sundsvall	Örnsköldsvik	SUB	-25.800000	1177.683887	127
22	Vetlanda	Växjö	SUB	-6.900000	143.305429	72
23	Borås	Varberg	SUB	-10.299998	260.758745	84
24	Haparanda	Luleå	SUB	4.600000	210.858567	124
25	Luleå	Skellefteå	SUB	15.100000	742.410242	133
26	Stockholm	Uppsala	SUB	7.000000	136.873721	69
27	Kristianstad	Växjö	SUB	3.000000	134.707658	120
28	Falun	Sandviken	SUB	2.300000	48.115171	65
29	Norrköping	Örebro	SUB	1.700000	72.868542	111
30	Gävle	Uppsala	SUB	-8.900000	140.802752	60
31	Sandviken	Örebro	CORE	48.000000	1789.999980	179
32	Helsingborg	Malmö	SUB	-3.900000	67.318060	60
33	Göteborg	Uddevalla	SUB	5.800000	117.417503	70
34	Malmö	Trelleborg	SUB	-1.300000	18.150077	34
35	Jönköping	Skövde	SUB	14.200000	337.352659	81
36	Hudiksvall	Sundsvall	SUB	-27.400000	641.652304	81
37	Västerås	Örebro	SUB	1.400000	49.705664	93
38	Borås	Skövde	SUB	10.999998	384.262722	105
39	Kalmar	Vetlanda	SUB	4.000000	174.202753	119

core_cost = sum(edge_info[edge_info['Type'] == 'CORE']['Cost'])
subnet_cost = sum(edge_info[edge_info['Type'] == 'SUB']['Cost'])
total_cost = core_cost + subnet_cost

print(f'core   = {core_cost:>9.3f}')
print(f'subnet = {subnet_cost:>9.3f}')
print('------------------')
print(f'total  = {total_cost:>9.3f}')
assert abs(autonomax.model.getObjective().getValue() - total_cost) < 1e-6

core   =  4430.000
subnet =  8948.777
------------------
total  = 13378.777

visualization.show(pd.DataFrame(autonomax.city_info()), pd.DataFrame(autonomax.edge_info()))